﻿#include<iostream>
#include<vector>

using namespace std;
namespace Ehundred
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& d1,const T& d2)
		{
			return d1 < d2;
		}
	};

	template<class T>
	class greater
	{
	public:
		bool operator()(const T& d1,const T& d2)
		{
			return d1 > d2;
		}
	};

	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:c(first,last)
		{
			for (int i = (c.size() - 2) / 2; i >= 0; i--)
			{
				int parent = i;
				int child = parent * 2 + 1;
				while (child < c.size())
				{
					if (child + 1 < c.size() && comp(*(c.begin() + child), *(c.begin() + child+1)))
					{
						child++;
					}
					if (comp(*(c.begin() + child), *(c.begin() + parent)))
					{
						break;
					}
					std::swap(*(c.begin() + child), *(c.begin() + parent));
					parent = child;
					child = parent * 2 + 1;
				}
			}
		}

		bool empty() const
		{
			return c.empty();
		}

		size_t size() const
		{
			return c.size();
		}

		const T& top() const
		{
			return *(c.begin());
		}

		void push(const T& x)
		{
			c.push_back(x);
			int child = c.size()-1;
			int parent = (child - 1) / 2 ;
			while (child>0)
			{
				if (comp(*(c.begin() + child), *(c.begin() + parent)))
				{
					break;
				}
				std::swap(*(c.begin() + child), *(c.begin() + parent));
				child = parent;
				parent = (child - 1) / 2;
			}
		}

		void pop()
		{
			std::swap(*(c.begin()), *(c.end() - 1));
			c.pop_back();
			int parent = 0;
			int child = parent * 2 + 1;
			while (child < c.size())
			{
				if (child + 1 < c.size() && comp(*(c.begin() + child), *(c.begin() + child+1)))
				{
					child++;
				}
				if (comp(*(c.begin() + child), *(c.begin() + parent)))
				{
					break;
				}
				std::swap(*(c.begin() + child), *(c.begin() + parent));
				parent = child;
				child = parent * 2 + 1;
			}
		}

	private:

		Container c;

		Compare comp;
	};
}


int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(5);
	v.push_back(4);
	v.push_back(3);

	Ehundred::priority_queue<int> q1(v.begin(), v.end());

	while (!q1.empty())
	{
		std::cout << q1.top() << ' ';
		q1.pop();

	}
}

